package SlidingWindow;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Hua YY
 * Date: 2024-10-26
 * Time: 19:51
 */


class Solution8 {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ret = new ArrayList<Integer>();
        //先把words中的元素放到HashMap中//每个元素的长度为m，数组长度为n,记录元素种类ele
        Map<String,Integer> hash1 = new HashMap<String,Integer>();
        int m = words[0].length() , n = words.length ,ele = 0;
        for(String ss : words){
            hash1.put(ss,hash1.getOrDefault(ss,0)+1);

        }



        for(int i = 0 ; i < m ; i++ ){
            //wc太绝了hashMap每次i移动时需要初始化一下，要不然上一次的值还存留在HashMap中
            Map<String,Integer> hash2 = new HashMap<String,Integer>();
            for(int left = i , right = i , count = 0 ; right + m <= s.length()  ; right += m){
                //进窗口
                String in = s.substring(right,right+m);
                hash2.put(in,hash2.getOrDefault(in,0)+1);
                //判断count加不加
                if(hash2.get(in) <= hash1.getOrDefault(in,0)){
                    count++;
                }
                //出窗口
                while(right - left + 1 > m * n ){
                    String out = s.substring(left,left+m);
                    left+=m;
                    if(hash2.get(out) <= hash1.getOrDefault(out,0)){
                        count--;
                    }
                    hash2.put(out,hash2.get(out)-1);
                }
                if(count == n){
                    ret.add(left);
                }


            }
        }
        return ret;

    }
}




public class Test8 {
    public static void main(String[] args) {
        Solution8 test = new Solution8();
        String s = "aaaaaaaaaaaaaa";
        String[] words = new String[]{"aa","aa"};
        test.findSubstring(s,words);
    }


}


































